
//#include <iostream>
//#include <stdlib.h>
//#include <strings.h>
//#include <ctype.h>
//#include <string.h>
//#include <stdio.h>
//#include "EfficientMap.cc"
//#include "TwoWayList.cc"
//#include "Types.cc"

#ifndef _BLOCK_SORTED_TEMP_TABLE
#define _BLOCK_SORTED_TEMP_TABLE

#include <vector>
#include <algorithm>
#include <queue>

static char *
strCatAlloc(char *s1, int l1, char *s2, int l2)
{
    char *cat = (char *) malloc((l1 + l2 + 1) * sizeof(char));
    if (cat == NULL)
    {
	fprintf(stderr, "ERROR: strCatAlloc unable to allocat cat.\n");
	exit(-1);
    }
    strcpy(cat, s1);
    strcpy(cat + l1, s2);

    return cat;
}

// TODO: Make this a configurable parameter or enhance it to be based on a static
// parameter that is the size of memory and then divide by the size of a record.
static const int MAX_RECORDS_PER_BLOCK = 30000000;

/*
 * The process for using this class is to call:
 *   BlockSortedTempTable bstt(tableFileName);
 *   bstt.writeBlocks();
 *   bstt.initForRead();
 *   InRecord r;
 *   while (bstt.next(r)) {
 *     // process r
 *   }
 *   bstt.cleanup();
 *
 * This class could be enhanced to operate more like a priority queue with
 * internal buffering of the top record using top() and pop() functions. That
 * might making the code for TPJoin.cc easier to work with.
 */
template <class TInRecord>
class BlockSortedTempTable
{

public:

    int blockCount;

    char *inputFile;
    int inputFileLen;

    bool readInitialized;

    class BlockIdxWrapper
    {

    public:

	int blockNum;
	BlockSortedTempTable *bstt;

	// Noop constructor for use by the priority queue
	BlockIdxWrapper() { }

	BlockIdxWrapper(int block, BlockSortedTempTable *b)
	{
	    blockNum = block;
	    bstt = b;
	}

	bool operator()(BlockIdxWrapper * &a, BlockIdxWrapper * &b)
	{
	    if (b->bstt->files->at(b->blockNum) == NULL)
	    {
		return true;
	    }
	    else if (a->bstt->files->at(a->blockNum) == NULL)
	    {
		return false;
	    }

	    return !(a->bstt->inputRecords->at(a->blockNum) <
		     b->bstt->inputRecords->at(b->blockNum));
	}
    };

    std::priority_queue<BlockIdxWrapper *, std::vector<BlockIdxWrapper *>,
	BlockIdxWrapper> *priorityQueue;
    std::vector<FILE *> *files;
    std::vector<TInRecord> *inputRecords;
    std::vector<char *> *blockTempFileNames;

    BlockSortedTempTable(char *inputFileName)
    {
	if (inputFileName == NULL)
	{
	    fprintf(stderr, "ERROR: BlockSortedTempTable constructure received NULL "
		    "inputFileName.\n");
	    exit(-1);
	}

	inputFile = strdup(inputFileName);
	if (inputFile == NULL)
	{
	    fprintf(stderr, "ERROR: BlockSortedTempTable unable to duplicate "
		    "inputFileName.\n");
	    exit(-1);
	}

	inputFileLen = strlen(inputFile);

	blockCount = 0;
    
	readInitialized = false;

	priorityQueue = NULL;
	files = NULL;
	inputRecords = NULL;
    }

    ~BlockSortedTempTable(void)
    {
	if (inputFile != NULL)
	{
	    free(inputFile);
	}

	if (priorityQueue != NULL)
	{
	    while (priorityQueue->size() > 0)
	    {
		BlockIdxWrapper *biw = priorityQueue->top();
		priorityQueue->pop();
		if (biw != NULL)
		{
		    delete biw;
		}
	    }

	    delete priorityQueue;
	}

	if (files != NULL)
	{
	    for (int blockIdx = 0; blockIdx < blockCount; blockIdx++)
	    {
		if (files->at(blockIdx) != NULL)
		{
		    fclose(files->at(blockIdx));
		}
	    }
	    delete files;
	}

	if (inputRecords != NULL)
	{
	    delete inputRecords;
	}

	if (blockTempFileNames != NULL)
	{
	    delete blockTempFileNames;
	}
    }

    /*
     * Initialize this block sorted temp table by sorting it into blocks and writing
     * the blocks to files on disk.
     */
    void writeBlocks(void)
    {
	if (blockCount != 0)
	{
	    fprintf(stderr, "ERROR: BlockSortedTempTable.writeBlocks called multiple "
		    "times.\n");
	    exit(-1);
	}

	FILE *inFile = fopen(inputFile, "r");
	if (inFile == NULL)
	{
	    fprintf(stderr, "ERROR: Unable to open file %s for reading.\n", inputFile);
	    exit(-1);
	}

	// Initialize the vector of temporary file names
	blockTempFileNames = new std::vector<char *>();

	// Initialize vector to hold records
	std::vector<TInRecord> *records = new std::vector<TInRecord>();
	records->reserve(MAX_RECORDS_PER_BLOCK);

	// Read the records and store them in the vector.
	TInRecord myRec;
	int counter = 0;
	while (myRec.ReadIn(inFile))
	{
	    records->push_back(myRec);
	    counter++;

	    if (records->size() == MAX_RECORDS_PER_BLOCK)
	    {
		sortAndWriteBlock(records);
		records->clear();
	    }
	}

	fclose(inFile);

	if (records->size() > 0)
	{
	    sortAndWriteBlock(records);
	    records->clear();
	}

	delete records;

	if (blockCount == 0)
	{
	    printf("WARNING: Read no records.");
	}
    }

    void initForRead(void)
    {
	if (readInitialized == true)
	{
	    fprintf(stderr, "ERROR: Called BlockSortedTempTable.initForRead twice.\n");
	    exit(-1);
	}

	readInitialized = true;

	priorityQueue = new std::priority_queue<BlockIdxWrapper *,
	    std::vector<BlockIdxWrapper *>, BlockIdxWrapper>();

	files = new std::vector<FILE *>();
	files->reserve(blockCount);
	    
	inputRecords = new std::vector<TInRecord>();
	inputRecords->reserve(blockCount);

	for (int blockIdx = 0; blockIdx < blockCount; blockIdx++)
	{
	    char sFileNum[10];
	    int numLen = snprintf(sFileNum, sizeof(sFileNum), "%d", blockIdx);
	    //char *filename = strCatAlloc(inputFile, inputFileLen, sFileNum, numLen);
	    char *filename = blockTempFileNames->at(blockIdx);

	    FILE *f = fopen(filename, "r");
	    if (f == NULL)
	    {
		fprintf(stderr, "ERROR: BlockSortedTempTable.initForRead unable to open "
			"file %s for read.\n", filename);
		exit(-1);
	    }

	    files->push_back(f);
	    TInRecord r;
	    bool b = r.ReadIn(f);
	    if (b == false)
	    {
		fprintf(stderr, "ERROR: BlockSortedTemptable.initForRead unable to read "
			"record out of block %d.", blockIdx);
		exit(-1);
	    }

	    inputRecords->push_back(r);

	    BlockIdxWrapper *biw = new BlockIdxWrapper(blockIdx, this);
	    priorityQueue->push(biw);
	}
    }

    bool isEmpty(void)
    {
	// TODO: Write thie function when enhancing BlockSortedTempTable's interface
	// to include record buffering
    }

    bool next(TInRecord &record)
    {
	if (priorityQueue->size() == 0)
	{
	    return false;
	}

	BlockIdxWrapper *nextBiw = priorityQueue->top();
	int nextBlockIdx = nextBiw->blockNum;
	priorityQueue->pop();

	record = inputRecords->at(nextBlockIdx);

	bool hasNext = (inputRecords->at(nextBlockIdx)).ReadIn(files->at(nextBlockIdx));
	if (hasNext == false)
	{
	    fclose(files->at(nextBlockIdx));
	    files->at(nextBlockIdx) = NULL;
	}
	else
	{
	    priorityQueue->push(nextBiw);
	}

	return true;
    }

    void cleanup(void)
    {
	for (std::vector<char *>::iterator it = blockTempFileNames->begin();
	     it < blockTempFileNames->end(); ++it)
	{
	    if (unlink(*it) != 0)
	    {
		fprintf(stderr, "ERROR: Unable to remove temporary file %s.\n", *it);
		exit(-1);
	    }
	    free(*it);
	}
    }

private:

    void sortAndWriteBlock(std::vector<TInRecord> *records)
    {
	blockCount++;

	char sFileNum[10];
	int numLen = snprintf(sFileNum, sizeof(sFileNum), "%d", blockCount - 1);
	char *outFileName = strCatAlloc(inputFile, inputFileLen, sFileNum, numLen);
	blockTempFileNames->push_back(outFileName);

	FILE *outFile = fopen(outFileName, "w");
	if (outFile == NULL)
	{
	    fprintf(stderr, "ERROR: writeSortedFile unable to open outFile %s.\n",
		    outFileName);
	    exit(-1);
	}

	// Sort the records
	std::sort(records->begin(), records->end());

	// Write the sorted records out
	for (typename std::vector<TInRecord>::iterator it = records->begin();
	     it < records->end(); it++)
	{
	    (*it).WriteBuffer(outFile);
	}

	fclose(outFile);
	//free(outFileName);
    }
};

#endif
